/**
 * Implementation of a Heap.
 *                                                               
 * @author M. Shearer                                            
 * @author <a href="mailto:shearm@sage.edu">shearm@sage.edu</a>  
 * @version 1.0                                                  
 */                                                              

@SuppressWarnings("unchecked")

public class Heap<E extends Comparable<? super E>> {
    // Data members
    private HeapNode<E>[] array;
    private int capacity;
    private int size;

    // Default capacity
    private static final int DEFAULT_SIZE = 25;


    /** Constructs an empty heap with a capacity of 25      
     *                                                      
     */                                                     
    public Heap() {
 this( DEFAULT_SIZE );
    }


    /** Constructs an empty heap with the specified initial
     *  capacity.
     *                                                         
     * @param max the initial capacity of the vector
     */                                                         
    public Heap( int max ) {
 array    =  new HeapNode[max];
 capacity = max;
 size     = 0;
    }


    /** Tests if this heap has no components
     *                                        
     */                                       
    public boolean isEmpty() {
 return ( size == 0 );
    }


    /** Returns the number of elements in this heap.
     *                                              
     */                                             
    public int size() {                         
        return ( size );                     
    }

                                               
    /** Insert an item in the heap
     *                                                   
     *  @param key the priority associated with the data.        
     *  @param data to be inserted in the heap.        
     */                                                  
    public boolean insert( int key, E data ) {
 if( size == capacity )
     return ( false );

 HeapNode<E> newNode = new HeapNode<E>( key, data );
 array[size] = newNode;
 trickleUp( size++ );

 return ( true );
    }


    /** Remove and return the data with the highest priority.
     *                                              
     */                                             
    public HeapNode<E> remove() {
 HeapNode<E> root = array[0];
 array[0] = array[--size];
 trickleDown( 0 );

 return ( root );
    }


    /** Restore the heap property after an insertion.
     *                                              
     *  @param index where to start the operation.        
     */                                             
    private void trickleUp( int index ) {
 int parent = (index -1 ) / 2;
 HeapNode<E> bottom = array[index];

 // while( (index > 0) && (array[parent].compareTo( bottom) < 0 ) ) {
 while( (index > 0) && (array[parent].compareTo( bottom) > 0 ) ) {
     array[index] = array[parent];  // move it down
     index = parent;
     parent = (parent-1) / 2;
 }
 array[index] = bottom;
    }


    /** Restore the heap property after an removal.
     *                                              
     *  @param index where to start the operation.        
     */                                             
    private void trickleDown( int index ) {
 int largerChild;
 HeapNode<E> top = array[index];      // save root

 while( index < (size / 2) ) {        // while node has at
                                      // least one child,
     int leftChild = 2 * index + 1;
     int rightChild = leftChild + 1;
     // find larger child
     if( rightChild < size &&         // (rightChild exists?)
  // array[leftChild].compareTo(array[rightChild]) < 0 )
  array[leftChild].compareTo(array[rightChild]) > 0 )
  largerChild = rightChild;
     else
  largerChild = leftChild;
     // top >= largerChild?
     // if( top.compareTo(array[largerChild]) >= 0 )
     if( top.compareTo(array[largerChild]) <= 0 )
  break;
     // shift child up
     array[index] = array[largerChild];
     index = largerChild;             // go down
 }                                    // end while
 array[index] = top;                  // root to index
    }


    /**
     * Returns the data as a String.
     *
     * @return the internal data as a String.
     */
    public String toString() {
 String s = new String();
 s += "Contents: ";

 for( int m = 0; m < size; ++m )
     if( array[m] != null )
  s += array[m] + " ";
     else
  s += "-- ";
 s += '\n';

 // Heap format
 int nBlanks     = 32;
 int itemsPerRow = 1;
 int column      = 0;
 int j           = 0;                    // current item
 String dots     = "...............................";
 s += dots;
 s += dots;
 s += '\n';
 while( size > 0 ) {                     // for each heap item
     if( column == 0 )                   // first item in row?
  for( int k = 0; k < nBlanks; ++k )  // preceding blanks
      s += ' ';
     // display item
     // s += array[j].getKey();
     s += array[j];

     if( ++j == size )                   // done?
  break;

     if( ++column == itemsPerRow ) {     // end of row?
  nBlanks /= 2;                   // half the blanks
  itemsPerRow *= 2;               // twice the items
  column = 0;                     // start over on
  s += '\n';
     }
     else                                // next item on row
  for( int k = 0; k < (nBlanks * 2 - 2); ++k )
      s += ' ';
 }  // end while

 s += '\n';
 s += dots;
 s += dots;
 return ( s );
    }


    /**
     * Testing routine for the class.
     *                               
     * @param args Array of String arguments.
     */                                      
    public static void main( String[] args ) {
        System.out.println( "Hello from Heap" );

 Heap<String> h = new Heap<String>();
 h.insert( 2, "Data" );
 h.insert( 3, "Structures" );
 h.insert( 1, "Stack" );
 h.insert( 1, "Queue" );
 h.insert( 0, "List" );
 h.insert( 5, "Heap" );
 h.insert( 3, "Bag" );

 System.out.println( h.toString() );
 h.remove();
 System.out.println( h.toString() );
    }
}